<!doctype html public "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http://www.cs.rice.edu/~dorai/tex2page -->
<head>
<title>
Structure and Interpretation 
of Computer Programs
</title>
<link rel="stylesheet" type="text/css" href="book-Z-C.css" title=default>
<meta name=robots content="noindex,follow">
</head>
<body>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-8.html">previous</a></span><span>, <a href="book-Z-H-10.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

<a name="%_chap_1"></a>
<h1 class=chapter>
<div class=chapterheading><a href="book-Z-H-4.html#%_toc_%_chap_1">Chapter 1</a></div><p>
<a href="book-Z-H-4.html#%_toc_%_chap_1">Building Abstractions with Procedures</a></h1><p>

<p>
<div align=right> 
<table width=60%><tr><td>
<span class=epigraph>
<p>

The acts of the mind, wherein it exerts its power over simple ideas,
are chiefly these three: 1. Combining several simple ideas into one
compound one, and thus all complex ideas are made.  2. The second is
bringing two ideas, whether simple or complex, together, and setting
them by one another so as to take a view of them at once, without
uniting them into one, by which it gets all its ideas of relations.
3.  The third is separating them from all other ideas that accompany
them in their real existence: this is called abstraction, and thus all
its general ideas are made.<p>

<a name="%_idx_6"></a>John Locke, <em>An Essay Concerning Human Understanding</em>
(1690)<p>

</span>
</td></tr></table>
</div>

<p><p>

We are about to study the idea of a <a name="%_idx_8"></a><a name="%_idx_10"></a><em>computational process</em>.
Computational processes are abstract beings that inhabit computers.
As they evolve, processes manipulate other abstract things called <a name="%_idx_12"></a><em>data</em>.  The evolution of a process is directed by a pattern of rules
called a <a name="%_idx_14"></a><em>program</em>.  People create programs to direct processes.
In effect, we conjure the spirits of the computer with our spells.<p>

A computational process is indeed much like a sorcerer's idea of a
spirit.  It cannot be seen or touched.  It is not composed of matter
at all.  However, it is very real.  It can perform intellectual work.
It can answer questions.  It can affect the world by disbursing money
at a bank or by controlling a robot arm in a factory.  The programs we
use to conjure processes are like a sorcerer's spells.  They are
carefully composed from symbolic expressions in arcane and esoteric
<a name="%_idx_16"></a><em>programming languages</em> that prescribe the tasks we want our
processes to perform.<p>

A computational process, in a correctly working computer, executes
programs precisely and accurately.  Thus, like the sorcerer's
apprentice, novice programmers must learn to understand and to
anticipate the consequences of their conjuring.  Even small errors
(usually called <a name="%_idx_18"></a><em>bugs</em> or <a name="%_idx_20"></a><em>glitches</em>) in programs can have
complex and unanticipated consequences.<p>

Fortunately, learning to program is considerably less dangerous than
learning sorcery, because the spirits we deal with are conveniently
contained in a secure way.  Real-world programming, however,
requires care, expertise, and wisdom.  A small bug in a computer-aided
design program, for example, can lead to the catastrophic collapse of
an airplane or a dam or the self-destruction of an industrial robot.<p>

Master software engineers have the ability to organize programs so
that they can be reasonably sure that the resulting processes will
perform the tasks intended.  They can visualize the behavior of their
systems in advance.  They know how to structure programs so that
unanticipated problems do not lead to catastrophic consequences, and
when problems do arise, they can <a name="%_idx_22"></a><em>debug</em> their programs.  Well-designed
computational systems, like well-designed automobiles or nuclear
reactors, are designed in a modular manner, so that the parts can be
constructed, replaced, and debugged separately.<p>

<a name="%_sec_Temp_6"></a>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_6">Programming in Lisp</a></h4><p>

We need an appropriate language for describing processes, and we will
use for this purpose the programming language Lisp.  Just as our
everyday thoughts are usually expressed in our natural language (such
as English, French, or Japanese), and descriptions of quantitative
phenomena are expressed with mathematical notations, our procedural
thoughts will be expressed in Lisp.  <a name="%_idx_24"></a>Lisp was invented in the late
1950s as a formalism for reasoning about the use of certain kinds of
logical expressions, called <a name="%_idx_26"></a><em>recursion equations</em>, as a model for
computation.  The language was conceived by <a name="%_idx_28"></a>John McCarthy and is based
on his paper ``Recursive Functions of Symbolic Expressions and Their
Computation by Machine'' (McCarthy 1960).<p>

Despite its inception as a mathematical formalism, Lisp is a practical
programming language.  A Lisp <a name="%_idx_30"></a><em>interpreter</em> is a machine that
carries out processes described in the Lisp language.  The first Lisp
interpreter was implemented by <a name="%_idx_32"></a>McCarthy with the help of colleagues
and students in the Artificial Intelligence Group of the <a name="%_idx_34"></a>MIT Research
Laboratory of Electronics and in the MIT Computation
Center.<a name="call_footnote_Temp_7" href="#footnote_Temp_7"><sup><small>1</small></sup></a> <a name="%_idx_38"></a>Lisp, whose name is an acronym for LISt Processing,
was designed to provide symbol-manipulating capabilities for
attacking programming problems such as the symbolic differentiation
and integration of algebraic expressions.  It included for this
purpose new data objects known as atoms and lists, which most
strikingly set it apart from all other languages of the period.<p>

Lisp was not the product of a concerted design effort.  Instead, it
evolved informally in an experimental manner in response to users'
needs and to pragmatic implementation considerations.  Lisp's informal
evolution has continued through the years, and the community of Lisp
users has traditionally resisted attempts to promulgate any
``official'' definition of the language.  This evolution, together
with the flexibility and elegance of the initial conception, has
enabled Lisp, which is the second oldest language in widespread use
today (only <a name="%_idx_40"></a>Fortran is older), to continually adapt to encompass the
most modern ideas about program design.  Thus, Lisp is by now a family
of dialects, which, while sharing most of the original features, may
differ from one another in significant ways.  The dialect of Lisp used
in this book is called <a name="%_idx_42"></a><a name="%_idx_44"></a>Scheme.<a name="call_footnote_Temp_8" href="#footnote_Temp_8"><sup><small>2</small></sup></a><p>

Because of its experimental character and its emphasis on symbol
manipulation, <a name="%_idx_96"></a><a name="%_idx_98"></a><a name="%_idx_100"></a>Lisp was at first very inefficient for numerical
computations, at least in comparison with Fortran.  Over the years,
however, Lisp compilers have been developed that translate programs
into machine code that can perform numerical computations reasonably
efficiently.  And for special applications, Lisp has been used with
great effectiveness.<a name="call_footnote_Temp_9" href="#footnote_Temp_9"><sup><small>3</small></sup></a>  Although Lisp has not yet overcome its old reputation
as hopelessly inefficient, Lisp is now used in many applications where
efficiency is not the central concern.  For example, Lisp has become
a language of choice for operating-system shell languages and for
extension languages for editors and computer-aided design systems.<p>

If Lisp is not a mainstream language, why are we using it as the
framework for our discussion of programming?  Because the language
possesses <a name="%_idx_112"></a>unique features that make it an excellent medium for
studying important programming constructs and data structures and for
relating them to the linguistic features that support them.  The most
significant of these features is the fact that Lisp descriptions of
processes, called <a name="%_idx_114"></a><a name="%_idx_116"></a><em>procedures</em>, can
themselves be represented and manipulated as Lisp data.  The
importance of this is that there are powerful program-design
techniques that rely on the ability to blur the traditional
distinction between ``passive'' data and ``active'' processes.  As we
shall discover, Lisp's flexibility in handling procedures as data
makes it one of the most convenient languages in existence for
exploring these techniques.  The ability to represent procedures as
data also makes Lisp an excellent language for writing programs that
must manipulate other programs as data, such as the interpreters and
compilers that support computer languages.  Above and beyond these
considerations, programming in Lisp is great fun.<p>

<p><div class=smallprint><hr></div><p>
<div class=footnote><p><a name="footnote_Temp_7" href="#call_footnote_Temp_7"><sup><small>1</small></sup></a> The <em>Lisp 1 Programmer's Manual</em> appeared in
1960, and the <em>Lisp 1.5 Programmer's Manual</em> <a name="%_idx_36"></a>(McCarthy 1965)
was published in 1962.  The early history of Lisp is described in
McCarthy 1978.

<p><a name="footnote_Temp_8" href="#call_footnote_Temp_8"><sup><small>2</small></sup></a> The two dialects in which most
major Lisp programs of the 1970s were written are <a name="%_idx_46"></a><a name="%_idx_48"></a>MacLisp <a name="%_idx_50"></a>(Moon 1978;
<a name="%_idx_52"></a>Pitman 1983), developed at the <a name="%_idx_54"></a>MIT Project MAC, and <a name="%_idx_56"></a><a name="%_idx_58"></a>Interlisp
<a name="%_idx_60"></a>(Teitelman 1974), developed at <a name="%_idx_62"></a>Bolt Beranek and Newman Inc. and the
<a name="%_idx_64"></a>Xerox Palo Alto Research Center.  <a name="%_idx_66"></a><a name="%_idx_68"></a>Portable Standard Lisp <a name="%_idx_70"></a>(Hearn 1969;
<a name="%_idx_72"></a>Griss 1981) was a Lisp dialect designed to be easily portable
between different machines.  MacLisp spawned a number of subdialects,
such as <a name="%_idx_74"></a><a name="%_idx_76"></a>Franz Lisp, which was developed at the <a name="%_idx_78"></a>University of
California at Berkeley, and <a name="%_idx_80"></a><a name="%_idx_82"></a>Zetalisp (Moon 1981), which was based on a
special-purpose processor designed at the <a name="%_idx_84"></a>MIT Artificial Intelligence
Laboratory to run Lisp very efficiently.  The Lisp dialect used in
this book, called <a name="%_idx_86"></a>Scheme (Steele 1975), was invented in 1975 by <a name="%_idx_88"></a><a name="%_idx_90"></a>Guy
Lewis Steele Jr. and Gerald Jay Sussman of the MIT Artificial
Intelligence Laboratory and later reimplemented for instructional use
at MIT.  Scheme became an IEEE standard in 1990 (IEEE 1990).  The
<a name="%_idx_92"></a><a name="%_idx_94"></a>Common Lisp dialect (Steele 1982, Steele 1990) was developed by the
Lisp community to combine features from the earlier Lisp dialects
to make an industrial standard for Lisp.  Common Lisp became an ANSI
standard in 1994 (ANSI&nbsp;1994).

<p><a name="footnote_Temp_9" href="#call_footnote_Temp_9"><sup><small>3</small></sup></a> One such special application was a
breakthrough computation of scientific importance -- an integration of
the motion of the <a name="%_idx_102"></a><a name="%_idx_104"></a>Solar System that extended previous results by
nearly two orders of magnitude, and demonstrated that the dynamics of
the Solar System is chaotic.  This computation was made possible by
new integration algorithms, a special-purpose compiler, and a
special-purpose computer all implemented with the aid of software
tools written in Lisp <a name="%_idx_106"></a>(Abelson et al. 1992; <a name="%_idx_108"></a><a name="%_idx_110"></a>Sussman and
Wisdom 1992).

</div>

<p><div class=navigation>[Go to <span><a href="book.html">first</a>, <a href="book-Z-H-8.html">previous</a></span><span>, <a href="book-Z-H-10.html">next</a></span> page<span>; &nbsp;&nbsp;</span><span><a href="book-Z-H-4.html#%_toc_start">contents</a></span><span><span>; &nbsp;&nbsp;</span><a href="book-Z-H-38.html#%_index_start">index</a></span>]</div><p>

</body>
</html>
